Search

The cyclic graph Γ (S) of a semigroup S is the simple undirected graph whose vertex set is S and two vertices x , y are adjacent if the subsemigroup generated by x and y is monogenic. In this paper, we determine the clique number of Γ (S) for an arbitrary semigroup S. Further, we obtain the independence number of Γ (S) if S is a finite monogenic semigroup. At the final part of this paper, we give bounds for independence number of Γ (S) if S is a semigroup of bounded exponent and we also characterize the semigroups attaining the bounds. [ABSTRACT FROM AUTHOR]

Let G n , α be the set of all connected graphs of order n with independence number α. A graph is called the Q -minimizer graph (A -minimizer graph) if it attains the minimum signless Laplacian spectral radius (adjacency spectral radius) over all graphs in G n , α. In this paper, we first show that the Q -minimizer graph must be a tree for α ≥ ⌈ n 2 ⌉ , and then we derive seven propositions about the Q -minimizer graph. Moreover, when n − α is a constant, the structure of the Q -minimizer graph is characterized. The method of getting Q -minimizer graph in this paper is different from that of getting A -minimizer graph. As applications, we determine the Q -minimizer graphs for α = n − 1 , n − 2 , n − 3 and n − 4 , respectively. The results of α = n − 1 , n − 2 , n − 3 are consistent with that in Li and Shu (2010) [15] and the result of α = n − 4 is new. Interestingly, the Q -minimizer graph in G n , n − 4 is unique, which is exactly one of the A -minimizer graphs in G n , n − 4. [ABSTRACT FROM AUTHOR]

The concept of k -independent set, introduced by Fink and Jacobson in 1986, is a natural generalization of classical independence set. A k -independent set is a set of vertices whose induced subgraph has maximum degree at most k. The k -independence number of G , denoted by α k (G) , is defined as the maximum cardinality of a k -independent set of G. As a natural counterpart of the k -independence number, we introduced the concept of k -edge-independence number. An edge set M in E (G) is called k -edge-independent if the maximum degree of the subgraph induced by the edges in M is less or equal to k. The k -edge-independence number, denoted β k (G) , is defined as the maximum cardinality of a k -edge-independent set. In this paper, we study the Nordhaus–Gaddum-type results for the parameter α k (G) and β k (G). We obtain sharp upper and lower bounds of α k (G) + α r (G ¯) , α k (G) ⋅ α r (G ¯) , β k (G) + β r (G ¯) and β k (G) ⋅ β r (G ¯) for a graph G of order n. Some graph classes attaining these bounds are also given. [ABSTRACT FROM AUTHOR]

We consider the following problem: for a given graph G and two integers k and d, can we apply a fixed graph operation at most k times in order to reduce a given graph parameter π by at least d? We show that this problem is NP-hard when the parameter is the independence number and the graph operation is vertex deletion or edge contraction, even for fixed d = 1 and when restricted to chordal graphs. We give a polynomial time algorithm for bipartite graphs when the operation is edge contraction, the parameter is the independence number and d is fixed. Further, we complete the complexity dichotomy for H-free graphs when the parameter is the clique number and the operation is edge contraction by showing that this problem is NP-hard in (C 3 + P 1) -free graphs even for fixed d = 1 . When the operation is edge deletion and the parameter is the chromatic number, we determine the computational complexity of the associated problem for cographs and complete multipartite graphs. Our results answer several open questions stated in Diner et al. (Theor Comput Sci 746:49–72, 2012, https://doi.org/10.1016/j.tcs.2018.06.023). [ABSTRACT FROM AUTHOR]

The atom-bond sum-connectivity (ABS) index of a graph GG with edges e1,…,em{e}_{1},\ldots ,{e}_{m} is the sum of the numbers 1−2(dei+2)−1\sqrt{1-2{\left({d}_{{e}_{i}}+2)}^{-1}} over 1≤i≤m1\le i\le m, where dei{d}_{{e}_{i}} is the number of edges adjacent to ei{e}_{i}. In this article, we study the maximum values of the ABS index over graphs with given parameters. More specifically, we determine the maximum ABS index of connected graphs of a given order with a fixed (i) minimum degree, (ii) maximum degree, (iii) chromatic number, (iv) independence number, or (v) number of pendent vertices. We also characterize the graphs attaining the maximum ABS values in all of these classes.

AbstractA graph G is an integral sum graph (sum graph) if its vertices can be labeled with distinct integers (positive integers) so that e = uv is an edge of G if and only if the sum of the labels on vertices u and v is also a label in G. A graph G is perfect if the chromatic number of each of its induced subgraphs is equal to the clique number of the same. A simple graph G is of class 1 if its edge chromatic number and maximum degree are same. In this paper, we prove that integral sum graphs Gn, [Formula: see text] and [Formula: see text] over the label sets [Formula: see text] and [Formula: see text], respectively, are perfect graphs as well as of class 1 for [Formula: see text]. We also obtain a few structural properties of these graphs.

We continue the study of (tw , ω) -bounded graph classes, that is, hereditary graph classes in which the treewidth can only be large due to the presence of a large clique, with the goal of understanding the extent to which this property has useful algorithmic implications for the Maximum Independent Set and related problems. In the previous paper of the series [Dallard, Milanič, and Štorgel, Treewidth versus clique number. II. Tree-independence number, J. Comb. Theory, Ser. B, 164 (2024) 404–442], we introduced the tree-independence number , a min-max graph invariant related to tree decompositions. Bounded tree-independence number implies both (tw , ω) -boundedness and the existence of a polynomial-time algorithm for the Maximum Weight Independent Packing problem, provided that the input graph is given together with a tree decomposition with bounded independence number. In particular, this implies polynomial-time solvability of the Maximum Weight Independent Set problem. In this paper, we consider six graph containment relations—the subgraph, topological minor, and minor relations, as well as their induced variants—and for each of them characterize the graphs H for which any graph excluding H with respect to the relation admits a tree decomposition with bounded independence number. The induced minor relation is of particular interest: we show that excluding either a K 5 minus an edge or the 4-wheel implies the existence of a tree decomposition in which every bag is a clique plus at most 3 vertices, while excluding a complete bipartite graph K 2 , q implies the existence of a tree decomposition with independence number at most 2 (q − 1). These results are obtained using a variety of tools, including ℓ -refined tree decompositions, SPQR trees, and potential maximal cliques, and actually show that in the bounded cases identified in this work, one can also compute tree decompositions with bounded independence number efficiently. Applying the algorithmic framework provided by the previous paper in the series leads to polynomial-time algorithms for the Maximum Weight Independent Set problem in an infinite family of graph classes, each of which properly contains the class of chordal graphs. In particular, these results apply to the class of 1-perfectly orientable graphs, answering a question of Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius from 2019. [ABSTRACT FROM AUTHOR]

A k -CEC graph is a graph G which has connected domination number Yc(G) = k and Yc(G+uv) < k for every uv ∈ E(G). A k-CVC graph G is a 2-connected graph with γc(G) = k and γc(G - v) < k for any v ∈ V (G). A graph is said to be maximal k-CVC if it is both k-CEC and k-CVC. Let δ, κ, and α be the minimum degree, connectivity, and independence number of G, respectively. In this work, we prove that for a maximal 3-CVC graph, if α = κ, then κ = δ. We additionally consider the class of maximal 3-CVC graphs with α < κ and κ < δ, and prove that every 3-connected maximal 3-CVC graph when κ < δ is Hamiltonian connected. [ABSTRACT FROM AUTHOR]

A twirling channel is a quantum channel induced by a continuous unitary representation π = ∑ i ⊕ m i π i on a compact group G , where π i are inequivalent irreducible representations. Motivated by a recent work [ 8 ] on minimal mixed unitary rank of Φ π , we explore the connections of the independence number, zero-error capacity, quantum codes, orthogonality index and phase retrievability of the quantum channel Φ π with the irreducible representation multiplicities m i and the irreducible representation dimensions dim H π i . In particular, we show that the independence number of Φ π is the sum of the multiplicities, the orthogonal index of Φ π is exactly the sum of those representation dimensions, and the zero-error capacity is equal to log (∑ i = 1 d m i ). We also present a lower bound for the phase retrievability in terms of the minimal length of phase retrievable frames for ℂ n [ABSTRACT FROM AUTHOR]

In this paper, we study the class of graphs G m , n that have the same degree sequence as two disjoint cliques K m and K n , as well as the class G ¯ m , n of the complements of such graphs. The problems of finding a maximum clique and a maximum independent set are NP-hard on G m , n . Therefore, looking for upper and lower bounds for the clique and independence numbers of such graphs is a challenging task. In this article, we obtain such bounds, as well as other related results. In particular, we consider the class of regular graphs, which are degree-equivalent to arbitrarily many identical cliques, as well as such graphs of bounded degree. [ABSTRACT FROM AUTHOR]

Consider a graph on the non-singular matrices over a finite field, in which two distinct non-singular matrices are joined by an edge whenever their sum is singular. We prove an upper bound for the independence number of this graph. As a consequence, we obtain a lower bound for its chromatic number that significantly improves a previous result of Tomon. [ABSTRACT FROM AUTHOR]

Let $ m_GI $ m G I denote the number of Laplacian eigenvalues of a graph G in an interval I and let $ \alpha (G) $ α (G) denote the independence number of G. In this paper, we determine the classes of graphs that satisfy the condition $ m_G[0,n-\alpha (G)]=\alpha (G) $ m G [ 0 , n − α (G) ] = α (G) when $ \alpha (G)= 2 $ α (G) = 2 and $ \alpha (G)= n-2 $ α (G) = n − 2 , where n is the order of G. When $ \alpha (G)=2 $ α (G) = 2 , $ G \cong K_1 \nabla K_{n-m} \nabla K_{m-1} $ G ≅ K 1 ∇ K n − m ∇ K m − 1 for some $ m \geq 2 $ m ≥ 2. When $ \alpha (G)=n-2 $ α (G) = n − 2 , there are two types of graphs $ B(p,q,r) $ B (p , q , r) and $ B'(p,q,r) $ B ′ (p , q , r) of order n = p + q + r + 2, which we call the binary star graphs. Also, we show that the binary star graphs with p = r are determined by their Laplacian spectra. [ABSTRACT FROM AUTHOR]

In this paper, we determine the graphs which have the minimal spectral radius among all the connected graphs of order n and the independence number ⌈ n 2 ⌉ - 1. [ABSTRACT FROM AUTHOR]

A prime labeling of a simple undirected graph G is to assign unique integer labels from the set {1,2,...,|V(G)|} to each vertex such that any two adjacent vertices in the graph have labels that are relatively prime. Studying prime labeling in graphs can help us understand the structure and properties of graphs and prime labeling has potential applications in cryptography and network security. In this paper we investigate when some graphs that are constructed from wheels are prime graphs.

A graph $G$ is called semi square stable if $\alpha (G^{2})=i(G)$ where $%\alpha (G^{2})$ is the independence number of $G^{2}$ and $i(G)$ is the independent dominating number of $G$. A subset $S$ of the vertex set of a graph $G$ is an efficient dominating set if $S$ is an independent set and every vertex of $G$ is either in $S$ or adjacent to exactly one vertex of $%S. $In this paper, we show that every square stable graph has an efficient dominating set and if a graph has an efficient dominating set, then it is semi square stable. We characterize when the join and the corona product of two disjoint graphs are semi square sable graphs and when they have efficient dominating sets.

Let (P , ≤) be an atomic poset with the least element 0. The complement of the intersection graph of ideals of P , denoted by Γ (P) , is defined to be a graph whose vertices are all non-trivial ideals of P and two distinct vertices I and J are adjacent if and only if I ∩ J = { 0 }. In this paper, we consider the complement of the intersection graph of ideals of a poset. We prove that Γ (P) is totally disconnected or diam (Γ (P) \) ∈ { 1 , 2 , 3 } , where is the set of all isolated vertices of Γ (P). We show that g r (Γ (P)) ∈ { 3 , 4 , ∞ }. Also, we characterize all posets whose complement of the intersection graph is forest, unicyclic or complete r -partite graph. Among other results, we prove that Γ (P) is weakly perfect; and it is perfect if and only if | Atom (P) | ≤ 4. Finally, we show that Γ (P) is class 1 , where P = Atom (P) ∪ { 0 }. [ABSTRACT FROM AUTHOR]

In this paper, we prove that every simple connected graph with α > n 2 has 1 as a normalized Laplacian eigenvalue with multiplicity at least 2 α − n , where n and α are the order and the independence number of the graph, respectively. Then we investigate graphs with α ≤ n 2 and having or not having 1 as a normalized Laplacian eigenvalue. [ABSTRACT FROM AUTHOR]

In this paper, we give a class of graphs that do not admit disjoint maximum and maximal independent (MMI) sets. The concept of inverse independence was introduced by Bhat and Bhat in [Inverse independence number of a graph, Int. J. Comput. Appl. 42(5) (2012) 9–13]. Let A be a α -set in G. An independent set D ⊂ V (G) − A is called an inverse independent set with respect to A. The inverse independence number α − 1 (G) is the size of the largest inverse independent set in G. Bhat and Bhat gave few bounds on the independence number of a graph, we continue the study by giving some new bounds and exact value for particular classes of graphs: spider tree, the rooted product and Cartesian product of two particular graphs. [ABSTRACT FROM AUTHOR]

Let G be a k-uniform hypergraph with vertex set V (G) and edge set E(G). A connected and acyclic hypergraph is called a supertree. For 0 ≤ α < 1, the α-spectral radius of G is the largest H-eigenvalue of αD(G) + (1 − α)A(G), where D(G) and A(G) are the diagonal tensor of the degrees and the adjacency tensor of G, respectively. In this paper, we determine the unique supertrees with maximum α-spectral radius among all k-uniform supertrees with m edges and independence number β for ⌈m(k−1)+1 k ⌉≤ β ≤ m, among all k-uniform supertrees with given degree sequences, and among all k-uniform supertrees with m edges and matching number μ for 1 ≤ μ ≤⌊m(k−1)+1 k ⌋, respectively. [ABSTRACT FROM AUTHOR]

We consider a family of distance graphs in R n and find its independence numbers in some cases. Define the graph J ± (n , k , t) in the following way: the vertex set consists of all vectors from { - 1 , 0 , 1 } n with exactly k nonzero coordinates; edges connect the pairs of vertices with scalar product t. We find the independence number of J ± (n , k , t) for an odd negative t and n > n 0 (k , t) . [ABSTRACT FROM AUTHOR]

The pairwise balanced designs (PBD's) is a pair (P;B), where P is a finite set of v points and B is a family of subsets of P, called blocks such that every two distinct points in P appear in exactly one block. Let α(G) = α and β(G) = β be the vertex covering and independence number of a graph G = (V;E) with the minimum and maximum cardinality of such sets are denoted by α-sets and β-sets of G, respectively (or, simply (α; β)-sets). In this paper, we obtain the total number of (α; β)-sets in different jump sizes of some circulant graphs apart from strongly regular graphs which are the blocks of PBD. [ABSTRACT FROM AUTHOR]

Let G$$ G $$ be an n$$ n $$‐vertex graph, where δ(G)≥δn$$ \delta (G)\ge \delta n $$ for some δ:=δ(n)$$ \delta := \delta (n) $$. A result of Bohman, Frieze and Martin from 2003 asserts that if α(G)=Oδ2n$$ \alpha (G)=O\left({\delta}^2n\right) $$, then perturbing G$$ G $$ via the addition of ωlog(1/δ)δ3$$ \omega \left(\frac{\log \left(1/\delta \right)}{\delta^3}\right) $$ random edges, a.a.s. yields a Hamiltonian graph. We prove several improvements and extensions of the aforementioned result. In particular, keeping the bound on α(G)$$ \alpha (G) $$ as above and allowing for δ=Ω(n−1/3)$$ \delta =\Omega \left({n}^{-1/3}\right) $$, we determine the correct order of magnitude of the number of random edges whose addition to G$$ G $$ a.a.s. yields a pancyclic graph. Moreover, we prove similar results for sparser graphs, and assuming the correctness of Chvátal's toughness conjecture, we handle graphs having larger independent sets. Finally, under milder conditions, we determine the correct order of magnitude of the number of random edges whose addition to G$$ G $$ a.a.s. yields a graph containing an almost spanning cycle. [ABSTRACT FROM AUTHOR]

Consider a simple graph $ \Gamma = (V(\Gamma), E(\Gamma)) $ with $ n $ vertices and $ m $ edges. Let $ P $ be a subset of $ V(\Gamma) $ and $ B(P) $ the set of neighbors of $ P $ in $ V(\Gamma)\backslash P $. In the study of graphs, the concept of differential refers to a measure of how much the number of edges leaving a set of vertices exceeds the size of that set. Specifically, given a subset $ P $ of vertices, the differential of $ P $, denoted by $ \partial(P) $, is defined as $ |B(P)|-|P| $. The differential of $ \Gamma $, denoted by $ \partial(\Gamma) $, is then defined as the maximum differential over all possible subsets of $ V(\Gamma) $. Additionally, the subdivision operator $ {{\mathcal{S}}({\Gamma})} $ is defined as the graph obtained from $ \Gamma $ by inserting a new vertex on each edge of $ \Gamma $. In this paper, we present results for the differential of graphs on the subdivision operator $ {{\mathcal{S}}({\Gamma})} $ where some of these show exact values of $ \partial({{\mathcal{S}}({\Gamma})}) $ if $ \Gamma $ belongs to a classical family of graphs. We obtain bounds for $ \partial({{\mathcal{S}}({\Gamma})}) $ involving invariants of a graph such as order $ n $, size $ m $ and maximum degree $ \Delta $, and we study the realizability of the graph $ \Gamma $ for any value of $ \partial({{\mathcal{S}}({\Gamma})}) $ in the interval $ \left[n-2, \frac{n(n-1)}{2}-n+2\right] $. Moreover, we give a characterization for $ \partial({{\mathcal{S}}({\Gamma})}) $ using the notion of edge star packing.

In this paper, we study the class of graphs Gm,n that have the same degree sequence as two disjoint cliques Km and Kn, as well as the class G¯m,n of the complements of such graphs. The problems of finding a maximum clique and a maximum independent set are NP-hard on Gm,n. Therefore, looking for upper and lower bounds for the clique and independence numbers of such graphs is a challenging task. In this article, we obtain such bounds, as well as other related results. In particular, we consider the class of regular graphs, which are degree-equivalent to arbitrarily many identical cliques, as well as such graphs of bounded degree.

Let S be a Clifford semigroup and A a subset of S. We write C a y (S , A) for the Cayley digraph of a Clifford semigroup S relative to A. The (weak, path, weak path) independence number of a graph is the maximum cardinality of an (weakly, path, weakly path) independent set of vertices in the graph. In this paper, we characterize maximal connected subdigraphs of C a y (S , A) and apply these results to determine the (weak, path, weak path) independence number of C a y (S , A) . [ABSTRACT FROM AUTHOR]

The independence number of a square matrix A , denoted by α (A) , is the maximum order of its principal zero submatrices. Given any integer n , let S n + be the set of n × n nonnegative symmetric matrices with zero diagonal. We characterize the linear maps on S n + preserving the independence number of all matrices in S n +. [ABSTRACT FROM AUTHOR]

For k ≥ 1 , the k -independence number α k of a graph is the maximum number of vertices that are mutually at distance greater than k. The well-known inertia and ratio bounds for the (1-)independence number α (= α 1) of a graph, due to Cvetković and Hoffman, respectively, were generalized recently for every value of k. We show that, for graphs with enough regularity, the polynomials involved in such generalizations are closely related and give exact values for α k , showing a new relationship between the inertia and ratio type bounds. Additionally, we investigate the existence and properties of the extremal case of sets of vertices that are mutually at maximum distance for walk-regular graphs. Finally, we obtain new sharp inertia and ratio type bounds for partially walk-regular graphs by using the predistance polynomials. [ABSTRACT FROM AUTHOR]

Let D(G) and A(G), respectively, be the diagonal matrix of vertex de- grees and the adjacency matrix of a connected graph G. The generalized adjacency matrix of G is defined as Aα(G) = αD(G) + (1 − α)A(G), α ∈ [0, 1]. The spread of the generalized adjacency matrix, denoted by S(Aα(G)), is defined as the difference of the largest and smallest eigenvalues of Aα(G). The spread S(Q(G)) of Q(G), the signless Laplacian matrix of G and S(A(G)) of A(G) are similarly defined. In this paper, we establish the relationships between S(Aα(G)), S(Q(G)) and S(A(G)). Further, we find bounds for S(Aα(G)) involving different parameters of G. Also, we obtain lower bounds for S(Aα(G)) in terms of the clique number and independence number of G, and we characterize the extremal graphs in some cases. [ABSTRACT FROM AUTHOR]

In view of this paper, we have defined Rough Co-zero divisor graph G (Z ∗ (J)) of a rough semiring (T , Δ , ∇) for a given approximation space I = (U , R) where U is nonempty finite set of objects and R is an arbitrary equivalence relation on U. It is proved that the Rough Co-zero divisor graph and the subgraph of Rough Ideal-based rough edge Cayley graph G (T ∗ (J)) are complement to each other. Also the Clique number and Independence number of G (T ∗ (J)) and G (Z ∗ (J)) are obtained. The developed concepts are illustrated with suitable examples. A sentiment analysis is also made using G (T ∗ (J)) for a Twitter data. [ABSTRACT FROM AUTHOR]

For a given graph H , the independence number α (H) of H is the size of the maximum independent set of V (H). Finding the maximum independent set in a graph is NP-hard. Another version of the independence number is defined as the size of the maximum-induced forest of H , and called the forest number of H , and denoted by f (H). Finding f (H) is also an NP-hard problem. Suppose that H = (V (H) , E (H)) is a graph, and is a family of graphs, a graph H has a -free k -coloring if there exists a decomposition of V (H) into sets V i , i = 1 , 2 , ... , k , so that G ⊈ H [ V i ] for each i , and each G ∈ . S ⊆ V (H) is G -free, if the subgraph of H induced by S is G -free, i.e., it contains no copy of G. Finding a maximum subset S of H , such that H [ S ] is a G -free graph is a very hard problem as well. In this paper, we study the generalized version of the independence number of a graph. Also, we give some bounds about the size of the maximum G -free subset of graphs as another purpose of this paper. [ABSTRACT FROM AUTHOR]

We propose new bounds on the domination number and on the independence number of a graph and show that our bounds compare favorably to recent ones. Our bounds are obtained by using the Bhatia-Davis inequality linking the variance, the expected value, the minimum, and the maximum of a random variable with bounded distribution. [ABSTRACT FROM AUTHOR]

The k-token graph Tk(G) is the graph whose vertices are the k-subsets of vertices of a graph G, with two vertices of Tk(G) adjacent if their symmetric difference is an edge of G. We explore when Tk(G) is a well-covered graph, that is, when all of its maximal independent sets have the same cardinality. For bipartite graphs G, we classify when Tk(G) is well-covered. For an arbitrary graph G, we show that if T2(G) is well-covered, then the girth of G is at most four. We include upper and lower bounds on the independence number of Tk(G), and provide some families of well-covered token graphs. [ABSTRACT FROM AUTHOR]

A graph G is called semi square stable if α(G²) = i(G) where α(G²) is the independence number of G² and i(G) is the independent dominating number of G. A subset S of the vertex set of a graph G is an efficient dominating set if S is an independent set and every vertex of G is either in S or adjacent to exactly one vertex of S: In this paper, we show that every square stable graph has an efficient dominating set and if a graph has an efficient dominating set, then it is semi square stable. We characterize when the join and the corona product of two disjoint graphs are semi square sable graphs and when they have efficient dominating sets. [ABSTRACT FROM AUTHOR]

Let T be a tree. The sets of leaves and branch vertices of T are denoted by L(T) and B(T), respectively. For two distinct vertices u, v of T, let P T [ u , v ] denote the unique path in T connecting u and v. When B (T) ≠ ∅ , we call the graph S T = ⋃ u , v ∈ B (T) P T [ u , v ] the internal subtree of T. In this paper, we give two conditions for a connected graph to have a spanning tree whose internal subtree has few branch vertices and leaves. Moreover, the sharpness of our result is also shown. [ABSTRACT FROM AUTHOR]

For a set H of connected graphs, a spanning subgraph H of G is called an H -factor of G if each component of H is isomorphic to an element of H . A graph G is called an H -factor uniform graph if for any two edges e 1 and e 2 of G, G has an H -factor covering e 1 and excluding e 2 . Let each component in H be a path with at least d vertices, where d ≥ 2 is an integer. Then an H -factor and an H -factor uniform graph are called a P ≥ d -factor and a P ≥ d -factor uniform graph, respectively. In this article, we verify that (i) a 2-edge-connected graph G is a P ≥ 3 -factor uniform graph if δ (G) > α (G) + 4 2 ; (ii) a (k + 2) -connected graph G of order n with n ≥ 5 k + 3 - 3 5 γ - 1 is a P ≥ 3 -factor uniform graph if | N G (A) | > γ (n - 3 k - 2) + k + 2 for any independent set A of G with | A | = ⌊ γ (2 k + 1) ⌋ , where k is a positive integer and γ is a real number with 1 3 ≤ γ ≤ 1 . [ABSTRACT FROM AUTHOR]

It was conjectured by Jaeger et al. that all 5-edge-connected graphs are $ Z_3 $-connected. In this paper, we confirm this conjecture for all 5-edge-connected graphs with independence number at most 3.

Let G be a finite group and A G be the automorphism group of G (i.e. Aut (G)). We associated a bipartite graph, denoted by Γ G , to G and its automorphism group Aut (G) as follows: two parts of the vertex set are G \ L (G , Z (G)) and A G \ Aut c (G) , where L (G , Z (G)) is the set of elements g ∈ G such that g − 1 α (g) ∈ Z (G) for all α ∈ A G and Aut c (G) is the set of automorphisms β ∈ A G such that g − 1 β (g) ∈ Z (G) for all g ∈ G. Two vertices g ∈ G \ L (G , Z (G)) and α ∈ A G \ Aut c (G) are adjacent if and only if g − 1 α (g) ∉ Z (G). In this paper, we investigate some fundamental properties of Γ G such as connectivity, diameter, girth, Hamiltonian, independence and dominating numbers. Moreover, planarity and outer planarity of the graph are studied. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with identity and Nil(R) be the set of nilpotent elements of R. The nil-graph of ideals of R is defined as the graph AG_N(R) whose vertex set is {I:(0)and there exists a non-trivial ideal such that and two distinct vertices and are adjacent if and only if . Here, we study conditions under which is complete or bipartite. Also, the independence number of is determined, where is a reduced ring. Finally, we classify Artinian rings whose nil-graphs of ideals have genus at most one.

Win proved a very famous conclusion that states the graph G with connectivity κ (G) , independence number α (G) and α (G) ≤ κ (G) + k − 1 (k ≥ 2) contains a spanning k-ended tree. This means that there exists a spanning tree with at most k leaves. In this paper, we strengthen the Win theorem to the following: Let G be a simple 2-connected graph such that | V (G) | ≥ 2 κ (G) + k , α (G) ≤ κ (G) + k (k ≥ 2) and the number of maximum independent sets of cardinality κ + k is at most n − 2 κ − k + 1 . Then, either G contains a spanning k-ended tree or a subgraph of K κ ∨ ((k + κ − 1) K 1 ∪ K n − 2 κ − k + 1) . [ABSTRACT FROM AUTHOR]

Simplicial complexes are a popular tool used to model higher-order interactions between elements of complex social and biological systems. In this paper, we study some combinatorial aspects of a class of simplicial complexes created by a graph product, which is an extension of the pseudo-fractal scale-free web. We determine explicitly the independence number, the domination number, and the chromatic number. Moreover, we derive closed-form expressions for the number of acyclic orientations, the number of root-connected acyclic orientations, the number of spanning trees, as well as the number of perfect matchings for some particular cases. [ABSTRACT FROM AUTHOR]

Let S be a connected graph with Steiner number S(S). A decomposition S = {S!, S", …, S#} is said to be a Steiner decomposition if S(G) = S(Gi) for all S (1 ≤ i ≤ n). The maximum cardinality obtained for the Steiner decomposition S of S is called the Steiner decomposition number of S and is denoted by S(G). In this paper we present a relation between Steiner decomposition number and independence number of S. Steiner decomposition number for some power of paths are discussed. It is also shown that given any pair S, S of positive integers with S ≥ 2 there exists a connected graph S such that G(S) = m and Sst (G) = n. [ABSTRACT FROM AUTHOR]

In this paper, we consider the relations between three degree-based graph invariants, namely, the second Zagreb index M 2 (G) , forgotten index F (G) and Lanzhou index L z (G) for a general graph G and a tree T. We prove that for a graph G with independence number α (G) , there exists F (G) − L z (G) 2 α (G) ≤ M 2 (G) ≤ F (G) + L z (G) 2 with both equalities holding if and only if G is the complete graph or empty graph. Moreover, we prove that for a tree T , there exists M 2 (T) ≤ F (T) + L z (T) 3 with equality if and only if T is the path of order 3. [ABSTRACT FROM AUTHOR]

A graph G is α -excellent if every vertex of G is contained in some maximum independent set of G. In this paper, we characterize α -excellent bipartite graphs, α -excellent unicyclic graphs, α -excellent simplicial graphs, α -excellent chordal graphs, α -excellent block graphs, and we show that every generalized Petersen graph is α -excellent. [ABSTRACT FROM AUTHOR]

Let f : V (G) → {0, 1, 2} be a function on a graph G with vertex set V (G). Let Vi = {v ∈ V (G) : f (v) = i} for every i ∈ {0, 1, 2}. The function f is said to be an independent Roman dominating function on G if V1 ∪ V2 is an independent set and for every υ 2 V0. The minimum weight among all independent Roman dominating functions f on G is the independent Roman domination number of G, and is denoted by iR(G). In this paper we continue with the study of this parameter. In particular, we provide new bounds on iR(G) in terms of other domination invariants. Some of our results are tight bounds that improve some well-known results. Finally, we compute the independent Roman domination number of some product graphs, and we provide an alternative proof to show that the problem of computing iR(G) is NP-hard. [ABSTRACT FROM AUTHOR]

Harary and Wiener indices are distance-based topological index. In this paper, we study the relations of graph energy e(G) and its Harary index H(G) and Wiener index W(G). Moreover, for a given graph G we study the lower bound of H(G) e(G) and W(G) e(G) in terms of the number of vertices of G. [ABSTRACT FROM AUTHOR]

The aim of the current research is to study and compare graphs authorship by Iranian researchers in Persian scientific research journals in the field of educational sciences by using algebraic parameters of mathematics. In this research, the data related to the scientific research documents of 336 Iranian researchers from 6 Persian scientific research journals in the field of educational sciences from 2017 to 2021 were extracted by using the issues printed in these journals and the graphs related to the authors of these journals have been drawn by mathematical methods and software, and then compared and analyzed by using algebraic parameters such as the average degrees of vertices, independence, color and matching numbers. In the main results, it was checked that the average grade of the Journal of the Educational Measurement and Evaluation Studies is 4.4 and higher than other journals. Also, the largest research group (cluster number) is 6 people, and the most research diversity (independence number) is 29 and it is related to of the Journal of the teaching research. Among the discussed journals in the field of educational sciences, according to the average grades, the amount of research cooperation of the Journal of Educational Measurement and Evaluation Studies is at a higher level than the other five journals.